package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 21:28 2020/8/19
 * @Description 按摩师
 * 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
 * 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
 * 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 */

public class Massage {

    /**
     *dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])  if i>=2
     * 因此在循环前先对dp[0] 和 dp[1]计算出来
     */
    public int massage(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], dp[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}
